\newpage
\appendix

%%附录第一个章节

\section{gr202.tsp测试数据更优路径}

经遗传算法计算，存在一条比给定的最优解路径更好的路径，这个路径如下：

[134, 170, 172, 168, 163, 164, 159, 160, 161, 165, 171, 173, 177, 179, 180, 181, 178, 182, 194, 195, 193, 192, 197, 201, 200, 199, 198, 196, 191, 190, 188, 176, 175, 174, 187, 189, 186, 185, 135, 133, 166, 115, 116, 101, 97, 100, 114, 113, 112, 121, 124, 125, 131, 132, 183, 184, 140, 139, 138, 142, 144, 147, 148, 149, 150, 151, 152, 154, 153, 146, 143, 24, 145, 17, 16, 8, 9, 10, 18, 20, 25, 26, 27, 28, 21, 22, 23, 141, 137, 136, 126, 127, 128, 129, 130, 38, 117, 39, 37, 36, 35, 41, 45, 40, 102, 105, 104, 103, 106, 107, 108, 109, 110, 98, 118, 119, 122, 123, 120, 111, 99, 95, 96, 94, 49, 48, 47, 46, 44, 43, 42, 34, 32, 33, 52, 55, 51, 54, 56, 59, 60, 61, 58, 57, 53, 50, 29, 30, 31, 19, 11, 14, 13, 12, 7, 6, 5, 3, 4, 1, 2, 15, 0, 74, 75, 73, 69, 68, 70, 72, 71, 63, 62, 64, 65, 67, 66, 83, 84, 85, 86, 91, 92, 93, 87, 88, 82, 77, 76, 78, 79, 81, 80, 89, 90, 156, 157, 162, 158, 155, 167, 169]

路径总长度为518.9478281，比给定最优解长度549.9980704更优。

\section{遗传算法源代码}
\begin{lstlisting}[language=python]
import random
import math
import io
import numpy as np
import matplotlib.pyplot as plt


class GA(object):
def __init__(self, num_city, num_total, iteration, data):
self.num_city = num_city
self.num_total = num_total
self.scores = []
self.iteration = iteration
self.location = data
self.ga_choose_ratio = 0.2
self.mutate_ratio = 0.2
# fruits中存每一个个体是下标的list
self.fruits = self.random_init(num_total, num_city)
self.dis_mat = self.compute_dis_mat(num_city, data)

# 显示初始化后的最佳路径
scores = self.compute_adp(self.fruits)
sort_index = np.argsort(-scores)
init_best = self.fruits[sort_index[0]]
init_best = self.location[init_best]
init_best = np.vstack((init_best, init_best[0]))
# plt.subplot(2, 2, 2)
# plt.title('init best result')
# plt.plot(init_best[:, 0], init_best[:, 1])

# 存储每个iteration的结果，画出收敛图
self.iter_x = [0]
self.iter_y = [1. / scores[sort_index[0]]]

def random_init(self, num_total, num_city):
tmp = [x for x in range(num_city)]
result = []
for i in range(num_total):
random.shuffle(tmp)
result.append(tmp.copy())
return result

# 计算不同城市之间的距离
def compute_dis_mat(self, num_city, location):
dis_mat = np.zeros((num_city, num_city))
for i in range(num_city):
for j in range(num_city):
if i == j:
dis_mat[i][j] = np.inf
continue
a = location[i]
b = location[j]
tmp = np.sqrt(sum([(x[0] - x[1]) ** 2 for x in zip(a, b)]))
dis_mat[i][j] = tmp
return dis_mat

# 计算路径长度
def compute_pathlen(self, path, dis_mat):
try:
a = path[0]
b = path[-1]
except:
import pdb
pdb.set_trace()
result = dis_mat[a][b]
for i in range(len(path) - 1):
a = path[i]
b = path[i + 1]
result += dis_mat[a][b]
return result

# 计算种群适应度
def compute_adp(self, fruits):
adp = []
for fruit in fruits:
if isinstance(fruit, int):
import pdb
pdb.set_trace()
length = self.compute_pathlen(fruit, self.dis_mat)
adp.append(1.0 / length)
return np.array(adp)

def swap_part(self, list1, list2):
index = len(list1)
list = list1 + list2
list = list[::-1]
return list[:index], list[index:]

def ga_cross(self, x, y):
len_ = len(x)
assert len(x) == len(y)
path_list = [t for t in range(len_)]
order = list(random.sample(path_list, 2))
order.sort()
start, end = order

# 找到冲突点并存下他们的下标,x中存储的是y中的下标,y中存储x与它冲突的下标
tmp = x[start:end]
x_conflict_index = []
for sub in tmp:
index = y.index(sub)
if not (index >= start and index < end):
x_conflict_index.append(index)

y_confict_index = []
tmp = y[start:end]
for sub in tmp:
index = x.index(sub)
if not (index >= start and index < end):
y_confict_index.append(index)

assert len(x_conflict_index) == len(y_confict_index)

# 交叉
tmp = x[start:end].copy()
x[start:end] = y[start:end]
y[start:end] = tmp

# 解决冲突
for index in range(len(x_conflict_index)):
i = x_conflict_index[index]
j = y_confict_index[index]
y[i], x[j] = x[j], y[i]

assert len(set(x)) == len_ and len(set(y)) == len_
return list(x), list(y)

def ga_parent(self, scores, ga_choose_ratio):
sort_index = np.argsort(-scores).copy()
sort_index = sort_index[0:int(ga_choose_ratio * len(sort_index))]
parents = []
parents_score = []
for index in sort_index:
parents.append(self.fruits[index])
parents_score.append(scores[index])
return parents, parents_score

def ga_choose(self, genes_score, genes_choose):
sum_score = sum(genes_score)
score_ratio = [sub * 1.0 / sum_score for sub in genes_score]
rand1 = np.random.rand()
rand2 = np.random.rand()
for i, sub in enumerate(score_ratio):
if rand1 >= 0:
rand1 -= sub
if rand1 < 0:
index1 = i
if rand2 >= 0:
rand2 -= sub
if rand2 < 0:
index2 = i
if rand1 < 0 and rand2 < 0:
break
return list(genes_choose[index1]), list(genes_choose[index2])

def ga_mutate(self, gene):
path_list = [t for t in range(len(gene))]
order = list(random.sample(path_list, 2))
start, end = min(order), max(order)
tmp = gene[start:end]
# np.random.shuffle(tmp)
tmp = tmp[::-1]
gene[start:end] = tmp
return list(gene)

def ga(self):
# 获得优质父代
scores = self.compute_adp(self.fruits)
# 选择部分优秀个体作为父代候选集合
parents, parents_score = self.ga_parent(scores, self.ga_choose_ratio)
tmp_best_one = parents[0]
tmp_best_score = parents_score[0]
# 新的种群fruits
fruits = parents.copy()
# 生成新的种群
while len(fruits) < self.num_total:
# 轮盘赌方式对父代进行选择
gene_x, gene_y = self.ga_choose(parents_score, parents)
# 交叉
gene_x_new, gene_y_new = self.ga_cross(gene_x, gene_y)
# 变异
if np.random.rand() < self.mutate_ratio:
gene_x_new = self.ga_mutate(gene_x_new)
if np.random.rand() < self.mutate_ratio:
gene_y_new = self.ga_mutate(gene_y_new)
x_adp = 1. / self.compute_pathlen(gene_x_new, self.dis_mat)
y_adp = 1. / self.compute_pathlen(gene_y_new, self.dis_mat)
# 将适应度高的放入种群中
if x_adp > y_adp and (not gene_x_new in fruits):
fruits.append(gene_x_new)
elif x_adp <= y_adp and (not gene_y_new in fruits):
fruits.append(gene_y_new)

self.fruits = fruits

return tmp_best_one, tmp_best_score
# draw 画图
def draw(self, points,path):
"""根据路径和点的坐标画图

Args:
points: 点的坐标列表
path:路径列表
"""
num = len(points)
plt.cla()
# plt.title("访问路径")
xs = [points[i][0] for i in range(num)]
ys = [points[i][1] for i in range(num)]
plt.scatter(xs,ys,color='b')
xs = np.array(xs)
ys = np.array(ys)
path = path
for i in range(num-1):
plt.plot(xs[[path[i],path[i+1]]],ys[[path[i],path[i+1]]],color = 'r')
plt.plot(xs[[path[num-1],path[0]]],ys[[path[num-1],path[0]]],color = 'r')
plt.scatter(xs[0],ys[0],color = 'azure',linewidths=5)
plt.pause(0.0001)

def run(self):
BEST_LIST = None
best_score = -math.inf

for i in range(1, self.iteration + 1):
tmp_best_one, tmp_best_score = self.ga()
self.iter_x.append(i)
self.iter_y.append(1. / tmp_best_score)
if tmp_best_score > best_score:
best_score = tmp_best_score
BEST_LIST = tmp_best_one
self.draw(self.location, BEST_LIST)
print(i)
print(1./best_score)
# plt.subplot(2, 2, 4)
# plt.title('convergence curve')
# plt.plot(self.iter_x, self.iter_y)
return self.location[BEST_LIST], 1. / best_score, BEST_LIST


# 读取数据
def read_tsp(path):
lines = open(path, 'r').readlines()
assert 'NODE_COORD_SECTION\n' in lines
index = lines.index('NODE_COORD_SECTION\n')
data = lines[index + 1:-1]
tmp = []
for line in data:
line = line.strip().split(' ')
if line[0] == 'EOF':
continue
tmpline = []
for x in line:
if x == '':
continue
else:
tmpline.append(float(x))
if tmpline == []:
continue
tmp.append(tmpline)
data = tmp
return data

def getBestPath(file):
"""从文件中获取最佳路径

Args:
file: 文件的路径

Returns:
访问节点的顺序

"""
with io.open(file,'r') as newfile:
path = []
flag = 0
for l in newfile.readlines():
if l.strip() == '-1':
break
if flag:
path.append((int(l.strip()))-1)
if l.strip() == 'TOUR_SECTION':
flag = 1
return path


data = read_tsp('./dataset/eil101.tsp')
BestPathfile = "./dataset/eil101.opt.tour"

data = np.array(data)
# plt.suptitle('GA in eil101.tsp')
data = data[:, 1:]
print(data)
# plt.subplot(2, 2, 1)
# plt.title('raw data')
show_data = np.vstack([data, data[0]])
# plt.plot(data[:, 0], data[:, 1])
Best, Best_path = math.inf, None

foa = GA(num_city=data.shape[0], num_total=50, iteration=5000, data=data.copy())
path, path_len, Best_list = foa.run()
plt.show()

if path_len < Best:
Best = path_len
Best_path = path
# plt.subplot(2, 2, 3)
# 加上一行因为会回到起点
plt.cla()
plt.subplot(1,2,1)
plt.title('GA result')
num = len(data)
print(num)
# plt.title("访问路径")
xs = [data[i][0] for i in range(num)]
ys = [data[i][1] for i in range(num)]
plt.scatter(xs,ys,color='b')
xs = np.array(xs)
ys = np.array(ys)

print(Best_list)

for i in range(num-1):
plt.plot(xs[[Best_list[i],Best_list[i+1]]],ys[[Best_list[i],Best_list[i+1]]],color = 'r')
plt.plot(xs[[Best_list[num-1],Best_list[0]]],ys[[Best_list[num-1],Best_list[0]]],color = 'r')
plt.scatter(xs[0],ys[0],color = 'azure',linewidths=5)

plt.subplot(1,2,2)
stdbestPath = getBestPath(BestPathfile) # 获取最佳路径
plt.title('True result')
plt.scatter(xs,ys,color='b')
for i in range(num-1):
plt.plot(xs[[stdbestPath[i],stdbestPath[i+1]]],ys[[stdbestPath[i],stdbestPath[i+1]]],color = 'r')
plt.plot(xs[[stdbestPath[num-1],stdbestPath[0]]],ys[[stdbestPath[num-1],stdbestPath[0]]],color = 'r')
plt.scatter(xs[0],ys[0],color = 'azure',linewidths=5)

plt.show()
\end{lstlisting}
